package leetcode.editor.cn.dsa10_recursion;
// 斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。
// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

public class FibonacciNumber509_2 {
    public static void main(String[] args) {
        Solution solution = new FibonacciNumber509_2().new Solution();
        System.out.println(solution.fib(2)); //1
        System.out.println(solution.fib(3)); //2
        System.out.println(solution.fib(4)); //3
        System.out.println(solution.fib(5)); //5
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 从2开始，每次把上一个元素的第二个数作为第一个数，
         * 上一个元素的两数之和作为第二个数
         * 1 ->2 ->3 ->4 ->5 ->6 ->7
         * 0   1   1   2   3   5   8
         * 1   1   2   3   5   8   13
         * @param N
         * @return
         */
        public int fib(int N) {
            if (N == 0) return 0;
            if (N == 1) return 1;
            int prev = 0; // 前一个元素的和
            int cur = 1; // 当前元素的和
            for (int i = 2; i <= N; i++) {
                // 每次遍历重新计算当前元素和以及前一个元素和
                int temp = cur; // 临时取出
                cur = cur + prev; // 更新当前元素的和
                prev = temp; // 更新上一个元素的和
            }
            return cur;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}